﻿#define _CRT_SECURE_NO_WARNINGS 1

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int* Left = (int*)malloc(sizeof(int) * numsSize);//Left[i]位置存储nums[i]左边元素的乘积
    int* Right = (int*)malloc(sizeof(int) * numsSize);//Right[i]位置存储nums[i]右边元素的乘积
    int* answer = (int*)malloc(sizeof(int) * numsSize);//存储Left和right的乘积
    if (Left == NULL || Right == NULL || answer == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    *returnSize = numsSize;
    Left[0] = 1;//第一个元素的左边乘积初始化为1
    for (int i = 1; i < numsSize; i++)
    {
        Left[i] = Left[i - 1] * nums[i - 1];//其余元素通过该公式计算
    }

    Right[numsSize - 1] = 1;//最后一个元素的右边乘积为1
    for (int i = numsSize - 2; i >= 0; i--)
    {
        Right[i] = nums[i + 1] * Right[i + 1];//其余元素通过该公式计算
    }

    for (int i = 0; i < numsSize; ++i)
    {
        answer[i] = Right[i] * Left[i];
    }
    return answer;
}

//进阶玩法:节省空间
int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int* answer = (int*)malloc(sizeof(int) * numsSize);//存储Left和right的乘积
    if (answer == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    *returnSize = numsSize;
    answer[0] = 1;//第一个元素的左边乘积初始化为1
    for (int i = 1; i < numsSize; i++)
    {
        answer[i] = answer[i - 1] * nums[i - 1];//其余元素通过该公式计算
    }

    int R = 1;//最后一个元素的右边乘积为1
    for (int i = numsSize - 1; i >= 0; i--)
    {
        answer[i] *= R;
        R *= nums[i];////其余元素通过该公式计算
    }

    return answer;
}





